Матч 184, Построение команд (TeamBuilder)

Дивизион 2, Уровень 3

Рассмотрим некоторую странную игру, в которой поле состоит из определенных мест, в которых могут находиться игроки. Известно, из каких мест и в какие можно передвигаться игрокам. При этом известно, что если из i существует путь в j, то не всегда из j можно попасть в i. Необходимо определить количество мест, из которых существуют пути во все остальные места, а также число мест, в которые можно попасть изо всех остальных мест.

Класс: TeamBuilder

Метод: vector<int> specialLocations(vector<string> paths)

Ограничения: paths содержит от 2 до 50 строк, содержащих n символов ‘0’ и ‘1’, paths[i][i] = 0.

Вход. Массив paths, представляющий собой матрицу, описывающую игровое поле.

Выход. Вектор, содержащий два целых числа: количество мест, из которых существуют пути во все остальные места, и число мест, в которые можно попасть изо всех остальных мест.

Пример входа

paths

{"010","000","110"}

{"0010","1000","1100","1000"}

{"01000","00100","00010","00001","10000"}

Пример выхода

{1,1}

{1,3}

{5,5}

РЕШЕНИЕ

транзитивное замыкание

Построим транзитивное замыкание матрицы смежности paths. Из вершины i можно попасть во все остальные вершины тогда и только тогда, когда i - ая строка матрица транзитивного замыкания содержит только единицы. В вершину j можно попасть изо всех остальных вершин тогда и только тогда, когда j - ый столбец матрицы транзитивного замыкания содержит только единицы. В задаче следует подсчитать количество таких строк и столбцов.

Количество единиц в строке будем подсчитывать при помощи функции count.

ПРОГРАММА

#include <cstdio>

#include <vector>

#include <string>

#include <algorithm>

using namespace std;

class TeamBuilder

{

public:

vector<int> specialLocations(vector<string> paths)

{

int k, i, j, n = paths.size();

vector<int> res(2,0);

for (k = 0; k < n; k++) paths[k][k] = '1';

for (k = 0; k < n; k++)

for (i = 0; i < n; i++)

for (j = 0; j < n; j++)

if (paths[i][k] == '1' && paths[k][j] == '1') paths[i][j] = '1';

for (k = 0; k < n; k++)

{

if (n == count(paths[k].begin(),paths[k].end(),'1')) res[0]++;

for (j = i = 0; i < n; i++) if (paths[i][k] == '1') j++;

if (j == n) res[1]++;

}

return res;

}

};